// 给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

//  

// 示例 1：

// 输入：[-4,-1,0,3,10]
// 输出：[0,1,9,16,100]
// 示例 2：

// 输入：[-7,-3,2,3,11]
// 输出：[4,9,9,49,121]
//  

// 提示：

// 1 <= A.length <= 10000
// -10000 <= A[i] <= 10000
// A 已按非递减顺序排序。


#include "stdc++.h"

// 双指针，从两端向中间遍历，有merge sort的思想
class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int n(A.size());
        vector<int> res(n, 0);
        int lhs{0};
        int rhs{n-1};
        int i{n-1};
        while (i >= 0) {
            if (A[lhs]*A[lhs] >= A[rhs]*A[rhs]) {
                res[i--] = A[lhs]*A[lhs];
                ++lhs;
            } else {
                res[i--] = A[rhs]*A[rhs];
                --rhs;
            }
        }
        return res;
    }
};

/* 平方再排序
时间复杂度：O(NlogN)
空间复杂度：O(logN)
*/
class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        vector<int> res(A);
        for (int& num : res) {
            num = num*num;
        }
        sort(res.begin(), res.end());
        return res;
    }
};

/* 双指针, 归并排序
*/
class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int n = A.size();
        int negative{-1}; // 最后一个负数的下标
        for (int i{0}; i < n; ++i) {
            if (A[i] < 0) {
                negative = i;
            } else {
                break;
            }
        }
        vector<int> res{};
        int i{negative}; // i -> 0
        int j{negative + 1}; // j -> n-1
        while (i >= 0 || j < n) {
            if (i < 0) { // i到最左边了
                res.push_back(A[j] * A[j]);
                ++j;
            } else if (j == n) { // j到最右边了
                res.push_back(A[i] * A[i]);
                --i;
            } else if (A[i] * A[i] < A[j] * A[j]) {
                res.push_back(A[i] * A[i]);
                --i;
            } else {
                res.push_back(A[j] * A[j]);
                ++j;
            }
        }
        return res;
    }
};

/* 双指针
从两边向中间，这样不需要考虑边界
*/
class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int n = A.size();
        vector<int> res(n, 0);
        for (int i{0}, j{n - 1}, pos{n - 1}; i <= j;) {
            if (A[i] * A[i] > A[j] * A[j]) {
                res[pos] = A[i] * A[i];
                ++i;
            } else {
                res[pos] = A[j]*A[j];
                --j;
            }
            --pos; // 从后往前放从大到小的元素
        }
        return res;
    }
};